﻿#define _CRT_SECURE_NO_WARNINGS 1
///**你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。
//
//为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。
//
//如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
//如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
//如果 k == 0 ，将第 i 个数字用 0 替换。
//由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。
//
//给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/defuse-the-bomb
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//* Note: The returned array must be malloced, assume caller calls free().
//*/
//int* decrypt(int* code, int codeSize, int k, int* returnSize){
//	int i = 0;
//	int j = 0;
//	int* a = (int*)malloc(sizeof(int)*codeSize);
//	memset(a, 0, sizeof(int)*codeSize);
//	*returnSize = codeSize;
//	if (k == 0)
//	{
//		return a;
//	}
//	else if (k>0)
//	{
//		for (i = 0; i<codeSize; i++)
//		{
//			int sum = 0;
//			int count = 0;
//			j = i + 1;
//			while (count<k)
//			{
//				j %= codeSize;
//				sum += code[j++];
//				count++;
//			}
//			a[i] = sum;
//		}
//	}
//	else
//	{
//		k = -k;
//		for (i = 0; i<codeSize; i++)
//		{
//			int sum = 0;
//			int count = 0;
//			j = i - 1;
//			while (count<k)
//			{
//				if (j<0)
//				{
//					j += codeSize;
//				}
//				sum += code[j--];
//				count++;
//			}
//			a[i] = sum;
//		}
//	}
//	return a;
//}






//
//给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
//
//请你返回排序后的数组。
//#define SIZE_MAX 201
//int hash[SIZE_MAX];
//int cmp(const void* a, const void* b)
//{
//	int a_ = *(int*)a + 100;
//	int b_ = *(int*)b + 100;
//	if (hash[b_] == hash[a_])
//	{
//		return b_ - a_;
//	}
//	return hash[a_] - hash[b_];
//}
///**
//* Note: The returned array must be malloced, assume caller calls free().
//*/
//int* frequencySort(int* nums, int numsSize, int* returnSize){
//	memset(hash, 0, sizeof(int)*SIZE_MAX);
//	int i = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		hash[nums[i] + 100]++;
//	}
//	qsort(nums, numsSize, sizeof(int), cmp);
//	*returnSize = numsSize;
//	return nums;
//}








//给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。

//给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/maximum-repeating-substring
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int maxRepeating(char * sequence, char * word){
//	int res = 0;
//	int lens = strlen(sequence);
//	int lenw = strlen(word);
//	for (int i = 0; i<lens; i++)
//	{
//		int j = i;
//		for (; j<lens&&sequence[j] == word[(j - i) % lenw]; j++);
//		res = fmax(res, (j - i) / lenw);
//	}
//	return  res;
//}








//请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和 / 或 "(al)" 按某种顺序组成。Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。然后，按原顺序将经解释得到的字符串连接成一个字符串。
//
//给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/goal-parser-interpretation
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char * interpret(char * command){
//	int len = strlen(command);
//	int j = 0;
//	char* a = (char*)malloc(sizeof(char)*(len + 1));
//	for (int i = 0; i<len; i++)
//	{
//		if (command[i] == 'G')
//		{
//			a[j++] = command[i];
//		}
//		if (command[i] == '(')
//		{
//			if (command[i + 1] == ')')
//			{
//				a[j++] = 'o';
//				i++;
//			}
//			else
//			{
//				a[j++] = 'a';
//				a[j++] = 'l';
//				i += 3;
//			}
//		}
//	}
//	a[j] = '\0';
//	return a;
//}








//给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。
//
//请你按下述方式重新格式化电话号码。
//
//首先，删除 所有的空格和破折号。
//其次，将数组从左到右 每 3 个一组 分块，直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
//2 个数字：单个含 2 个数字的块。
//3 个数字：单个含 3 个数字的块。
//4 个数字：两个分别含 2 个数字的块。
//最后用破折号将这些块连接起来。注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且 最多 生成两个含 2 个数字的块。
//
//返回格式化后的电话号码。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/reformat-phone-number
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char * reformatNumber(char * number){
//	int count = 0;
//	int i = 0;
//	int k = 0;
//	int len = strlen(number);
//	char* a = (char*)malloc(sizeof(char)*(len + len / 3 + 1));
//	for (i = 0; i<len; i++)
//	{
//		if (number[i] == '-' || number[i] == ' ')
//		{
//			continue;
//		}
//		if (k % 4 == 3)
//		{
//			a[k++] = '-';
//		}
//		a[k++] = number[i];
//	}
//	if (k % 4 == 1)
//	{
//		char tmp = a[k - 3];
//		a[k - 3] = '-';
//		a[k - 2] = tmp;
//	}
//	a[k] = '\0';
//	return a;
//}








//给你一个偶数长度的字符串 s 。将其拆分成长度相同的两半，前一半为 a ，后一半为 b 。
//
//两个字符串 相似 的前提是它们都含有相同数目的元音（'a'，'e'，'i'，'o'，'u'，'A'，'E'，'I'，'O'，'U'）。注意，s 可能同时含有大写和小写字母。
//
//如果 a 和 b 相似，返回 true ；否则，返回 false 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/determine-if-string-halves-are-alike
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int print(char p)
//{
//	if (p == 'a' || p == 'A' ||
//		p == 'e' || p == 'E' ||
//		p == 'i' || p == 'I' ||
//		p == 'o' || p == 'O' ||
//		p == 'u' || p == 'U')
//	{
//		return 1;
//	}
//	return 0;
//}
//bool halvesAreAlike(char * s){
//	int counta = 0;
//	int countb = 0;
//	int len = strlen(s);
//	for (int i = 0; i<len / 2; i++)
//	{
//		if (print(s[i]) == 1)
//		{
//			counta++;
//		}
//		if (print(s[len - i - 1]) == 1)
//		{
//			countb++;
//		}
//	}
//	if (counta == countb)
//	{
//		return true;
//	}
//	return false;
//}







//请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
//
//numberOfBoxesi 是类型 i 的箱子的数量。
//numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
//整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
//
//返回卡车可以装载 单元 的 最大 总数。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/maximum-units-on-a-truck
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int cmp(const void* a, const void* b)
//{
//	int* c = *(int**)a;
//	int* d = *(int**)b;
//	return d[1] - c[1];
//}
//int maximumUnits(int** boxTypes, int boxTypesSize, int* boxTypesColSize, int truckSize){
//	int res = 0;
//	int num = 0;
//	int* a = (int*)malloc(sizeof(int)*boxTypesSize);
//	qsort(boxTypes, boxTypesSize, sizeof(int*), cmp);
//	for (int i = 0; i<boxTypesSize; i++)
//	{
//		num = fmin(boxTypes[i][0], truckSize);
//		truckSize -= num;
//		res += num*boxTypes[i][1];
//	}
//	return res;
//}







//给你一个字符串 time ，格式为 hh : mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。
//
//有效的时间为 00 : 00 到 23 : 59 之间的所有时间，包括 00 : 00 和 23 : 59 。
//
//替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/latest-time-by-replacing-hidden-digits
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//char * maximumTime(char * time){
//	if (time[0] == '?')
//	{
//		if (time[1] == '?')
//		{
//			time[0] = '2';
//			time[1] = '3';
//		}
//		else if (time[1] >= '4')
//		{
//			time[0] = '1';
//		}
//		else if (time[1]<'4')
//		{
//			time[0] = '2';
//		}
//	}
//	if (time[1] == '?')
//	{
//		if (time[0]<'2')
//		{
//			time[1] = '9';
//		}
//		else
//		{
//			time[1] = '3';
//		}
//	}
//	if (time[3] == '?')
//	{
//		time[3] = '5';
//	}
//	if (time[4] == '?')
//	{
//		time[4] = '9';
//	}
//	return time;
//}








//给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
//
//如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/check-if-one-string-swap-can-make-strings-equal
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool areAlmostEqual(char * s1, char * s2){
//	int len1 = strlen(s1);
//	int len2 = strlen(s2);
//	if (len1 != len2)
//	{
//		return false;
//	}
//	int count = 0;
//	int i = 0;
//	char c1, c2;
//	for (i = 0; i<len1; i++)
//	{
//		if (s1[i] == s2[i])
//		{
//			continue;
//		}
//		if (count == 0)
//		{
//			c1 = s1[i];
//			c2 = s2[i];
//		}
//		else if (count == 1)
//		{
//			if (c1 != s2[i] || c2 != s1[i])
//			{
//				return false;
//			}
//		}
//		else if (count == 2)
//		{
//			return false;
//		}
//		count++;
//	}
//	return count != 1;
//}







//给你一个二进制字符串 s ，该字符串 不含前导零 。
//
//如果 s 最多包含 一个由连续的 '1' 组成的字段 ，返回 true​​​ 。否则，返回 false 。
//
//
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/check-if-binary-string-has-at-most-one-segment-of-ones
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool checkOnesSegment(char * s){
//	int i = 0;
//	int len = strlen(s);
//	if (len == 1)
//	{
//		return true;
//	}
//	for (i = 1; i<len; i++)
//	{
//		if (s[i] == '1'&&s[i - 1] == '0')
//		{
//			return false;
//		}
//	}
//	return true;
//}